package ext;

import org.junit.Test;

public class Muiltify {
    

    public String multi(char[] a, char[] b) {
        int m = a.length, n = b.length;
        int[] nums = new int[m + n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                nums[i + j] += (a[i] - '0') * (b[i] - '0');
            }
        }
        int len = m + n, t = 0;
        for (int i = 0; i < len - 1; i++) {
            nums[i] += t;
            t = nums[i] / 10;
            nums[i] %= 10;
        }
        int start = len - 2;
        if (t != 0) {
            nums[len - 1] = t;
            start = len - 1;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = start; i >= 0; i--) {
            sb.append(nums[i]);
        }
        return sb.toString();
    }

    //先升序后降序的二分查找
    public int find(int[] nums, int tar) {
        //1. 找到最大值的起始或者结束位置
        int n = nums.length, lo = 1, hi = n - 1;
        while (lo < hi) {
            int mid = (hi - lo) / 2 + lo;
            if (nums[mid] < nums[mid + 1]) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        int m = lo;
        //1. 在升序中查找元素
        lo = 0;
        hi = m;
        while (lo < hi) {
            int mid = (hi - lo) / 2 + lo;
            if (nums[mid] < tar) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        if (nums[lo] == tar) {
            return lo;
        }
        //1. 在降序中查找元素
        lo = m + 1;
        hi = n - 1;
        while (lo < hi) {
            int mid = (hi - lo) / 2 + lo;
            if (nums[mid] < tar) {
                hi = mid - 1;
            } else {
                lo = mid;
            }
        }

        return nums[lo] == tar ? lo : -1;

    }

    @Test
    public void test8() {
        int[] nums = new int[]{1,1,2,3,3,7,4,0, 0,-1};
        System.out.println(find(nums, 7));
    }

    @Test
    public void test() {
        char[] a = "99".toCharArray(), b = "999".toCharArray();
        System.out.println(multi(a, b));
        System.out.println(Integer.parseInt(new String(a)) * Integer.parseInt(new String(b)));
    }

}
